#include "../tools.h"

// 判断是否子序列
class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b){
            return a.size() != b.size() ? a.size() > b.size() : a < b;
        });

        int size_s = s.size();
        int size = dictionary.size();
        for(int i = 0; i < size; ++i){
            string word = dictionary[i];
            int is = 0, iw = 0;
            int size_w = word.size();
            while(is < size_s && iw < size_w){
                if(s[is] == word[iw]) ++iw;
                ++is;
            }
            // cout << word << ": " << is << " " << iw << endl;
            if(iw == size_w) return word;
        }


        return "";
    }
};

int main(int argc, char const *argv[])
{
    Solution sol;

    string str = "abpcplea";
    vector<string> dictionary = {"ale","apple","monkey","plea"};

    cout << sol.findLongestWord(str, dictionary) << endl;

    return 0;
}
